`:top
In `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f, `!frequent subtree mining`! is the problem of finding all patterns in a given database whose support (a metric related to its number of occurrences in other subtrees) is over a given threshold.`:cite-ref-chi01-1-0[`F5bf`_`[1`#cite-note-chi01-1]`_`f] It is a more general form of the `F33f`_`[maximum agreement subtree problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Maximum_agreement_subtree_problem]`_`f.`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]
>>Contents
• `F0af`_`[Definition`#definition]`_`f
• `F0af`_`[Formal definition`#formal-definition]`_`f
• `F0af`_`[TreeMiner`#treeminer]`_`f
• `F0af`_`[Definitions`#definitions]`_`f
• `F0af`_`[Algorithm`#algorithm]`_`f
• `F0af`_`[Applications`#applications]`_`f
• `F0af`_`[Challenges`#challenges]`_`f
• `F0af`_`[References`#references]`_`f
-─
>>Definition
Frequent subtree mining is the problem of trying to find all of the patterns whose "support" is over a certain user-specified level, where "support" is calculated as the number of trees in a database which have at least one subtree `F33f`_`[isomorphic`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_isomorphism]`_`f to a given pattern.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f]
>>>Formal definition
The problem of frequent subtree mining has been formally defined as:`:cite-ref-chi01-1-1[`F5bf`_`[1`#cite-note-chi01-1]`_`f]
Given a threshold `*minfreq`*, a class of trees C {\\displaystyle {\\mathcal {C}}} , a transitive subtree relation P ⪯ ⪯ T {\\displaystyle P\\preceq T} between trees P , T ∈ ∈ C {\\displaystyle P,T\\in {\\mathcal {C}}} , a finite set of trees D ⊆ ⊆ C {\\displaystyle {\\mathcal {D}}\\subseteq {\\mathcal {C}}} , the frequent subtree mining problem is the problem of finding all trees P ⊂ ⊂ C {\\displaystyle {\\mathcal {P}}\\subset {\\mathcal {C}}} such that no two trees in P {\\displaystyle {\\mathcal {P}}} are isomorphic and ∀ ∀ P ∈ ∈ P : f r e q ( P , D ) = ∑ ∑ T ∈ ∈ D d ( P , T ) ≥ ≥ m i n f r e q , {\\displaystyle \\forall P\\in {\\mathcal {P}}:\\quad \\mathrm {freq} (P,{\\mathcal {D}})=\\sum \\nolimits _{T\\in {\\mathcal {D}}}d(P,T)\\geq \\mathrm {minfreq} ,}
where d is an anti-monotone function such that if P ′ ⪯ ⪯ P {\\displaystyle P'\\preceq P} then ∀ ∀ T ∈ ∈ C : d ( P ′ , T ) ≥ ≥ d ( P , T ) . {\\displaystyle \\forall T\\in {\\mathcal {C}}:\\quad d(P',T)\\geq d(P,T).}
>>TreeMiner
In 2002, Mohammed J. Zaki introduced TreeMiner, an efficient algorithm for solving the frequent subtree mining problem, which used a "scope list" to represent tree nodes and which was contrasted with PatternMatcher, an algorithm based on pattern matching.`:cite-ref-0-4-0[`F5bf`_`[4`#cite-note-0-4]`_`f]
>>>Definitions
>>>>Induced sub-trees
A sub-tree S = ( V s , E s ) {\\displaystyle S=(V_{s},E_{s})} is an induced sub-tree of T = ( V , E ) {\\displaystyle T=(V,E)} if and only if V s ⊆ ⊆ V {\\displaystyle V_{s}\\subseteq V} and E s ⊆ ⊆ E {\\displaystyle E_{s}\\subseteq E} . In other words, any two nodes in S that are directly connected by an edge is also directly connected in T. For any node A and B in S, if node A is the parent of node B in S, then node A must also be the parent of node B in T.
>>>>Embedded sub-trees
A sub-tree S = ( V s , E s ) {\\displaystyle S=(V_{s},E_{s})} is an embedded sub-tree of T = ( V , E ) {\\displaystyle T=(V,E)} if and only if V s ⊆ ⊆ V {\\displaystyle V_{s}\\subseteq V} and two endpoint nodes of any edge in S are on the same path from the root to a leaf node in T. In other words, for any node A and B in S, if node A is the parent of node B in S, then node A must be an ancestor of node B in T. Any induced sub-trees are also embedded sub-trees, and thus the concept of embedded sub-trees is a generalization of induced sub-trees. As such embedded sub-trees characterizes the hidden patterns in a tree that are missing in traditional induced sub-tree mining. A sub-tree of size k is often called a k-sub-tree.
>>>>Support
The support of a sub-tree is the number of trees in a database that contains the sub-tree. A sub-tree is frequent if its support is not less than a user-specified threshold (often denoted as `*minsup).`* The goal of TreeMiner is to find all embedded sub-trees that have support at least the minimum support.
>>>>String representation of trees
There are several different ways of encoding a tree structure. TreeMiner uses string representations of trees for efficient tree manipulation and support counting. Initially the string is set to ∅ ∅ {\\displaystyle \\varnothing } . Starting from the root of the tree, node labels are added to the string in depth-first search order. -1 is added to the string whenever the search process backtracks from a child to its parent. For example, a simple binary tree with root labelled A, a left child labelled B and right child labelled C can be represented by a string A B -1 C -1.
>>>>Prefix equivalence class
Two k-sub-trees are said to be in the same prefix equivalence class if the string representation of them are identical up to the (k-1)-th node. In other words, all elements in a prefix equivalence class only differ by the last node. For example, two trees with string representation A B -1 C -1 and A B -1 D -1 are in the prefix equivalence class A B with elements (C, 0) and (D,0). An element of a prefix class is specified by the node label paired with the 0-based depth first index of the node it is attached to. In this example, both elements of prefix class A B are attached to the root, which has an index of 0.
>>>>Scope
The scope of a node A is given by a pair of numbers [ l , r ] {\\displaystyle [l,r]} where l and r are the minimum and maximum node index in the sub-tree rooted at A. In other words, l is the index of A, and r is the index of the rightmost leaf among the descendants of A. As such the index of any descendant of A must lie in the scope of A, which will be a very useful property when counting the support of sub-trees.
>>>Algorithm
>>>>Candidate generation
Frequent sub-tree patterns follow the anti-monotone property. In other words, the support of a k-sub-tree is less than or equal to the support of its (k-1)-sub-trees. Only super patterns of known frequent patterns can possibly be frequent. By utilizing this property, k-sub-trees candidates can be generated based on frequent (k-1)-sub-trees through prefix class extension. Let C be a prefix equivalence class with two elements (x,i) and (y,j). Let C' be the class representing the extension of element (x,i). The elements of C' are added by performing `*join`* operation on the two (k-1)-sub-trees in C. The `*join`* operation on (x,i) and (y,j) is defined as the following.
• If i > j {\\displaystyle i>j} , then add (y,j) to C'.
• If i = j {\\displaystyle i=j} , then add (y,j) and (y, ni) to C' where ni the depth-first index of x in C
• If i < j {\\displaystyle i<j} , no possible element can be added to C'
This operation is repeated for any two ordered, but not necessarily distinct elements in C to construct the extended prefix classes of k-sub-trees.
>>>>Scope-list representation
TreeMiner performs depth first candidate generation using scope-list representation of sub-trees to facilitate faster support counting. A k-sub-tree S can be representation by a triplet (t,m,s) where t is the tree id the sub-tree comes from, m is the prefix match label, and s the scope of the last node in S. Depending on how S occurs in different trees across the database, S can have different scope-list representation. TreeMiner defines `*scope-list join`* that performs class extension on scope-list representation of sub-trees. Two elements (x,i) and (y,j) can be joined if there exists two sub-trees ( t x , m x , s x ) {\\displaystyle (t_{x},m_{x},s_{x})} and ( t y , m y , s y ) {\\displaystyle (t_{y},m_{y},s_{y})} that satisfy either of the following conditions.
• In-scope test: t x = t y , m x = m y , s y ⊂ ⊂ s x {\\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}\\subset s_{x}} , which corresponds to the case when i = j {\\displaystyle i=j} .
• Out-scope test: t x = t y , m x = m y , s y > s x {\\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}} , which correspond to the case when i > j {\\displaystyle i>j} .
By keeping track of distinct tree ids used in the scope-list tests, the support of sub-trees can be calculated efficiently.
>>Applications
Domains in which frequent subtree mining is useful tend to involve complex relationships between data entities: for instance, the analysis of XML documents often requires frequent subtree mining.`:cite-ref-chi01-1-2[`F5bf`_`[1`#cite-note-chi01-1]`_`f] Another domain where this is useful is the web usage mining problem: since the actions taken by users when visiting a web site can be recorded and categorized in many different ways, complex databases of trees need to be analyzed with frequent subtree mining.`:cite-ref-0-4-1[`F5bf`_`[4`#cite-note-0-4]`_`f] Other domains in which frequent subtree mining is useful include `F33f`_`[computational biology`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_biology]`_`f,`:cite-ref-dee13-5-0[`F5bf`_`[5`#cite-note-dee13-5]`_`f]`:cite-ref-yun05-6-0[`F5bf`_`[6`#cite-note-yun05-6]`_`f] RNA structure analysis,`:cite-ref-yun05-6-1[`F5bf`_`[6`#cite-note-yun05-6]`_`f] pattern recognition,`:cite-ref-chi04-7-0[`F5bf`_`[7`#cite-note-chi04-7]`_`f] bioinformatics,`:cite-ref-xia03-8-0[`F5bf`_`[8`#cite-note-xia03-8]`_`f] and analysis of the `F33f`_`[KEGG`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=KEGG]`_`f GLYCAN database.`:cite-ref-9[`F5bf`_`[9`#cite-note-9]`_`f]
>>Challenges
Checking whether a pattern (or a transaction) supports a given subgraph is an `F33f`_`[NP-complete`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NP-complete]`_`f problem, since it is an NP-complete instance of the `F33f`_`[subgraph isomorphism problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Subgraph_isomorphism_problem]`_`f.`:cite-ref-chi04-7-1[`F5bf`_`[7`#cite-note-chi04-7]`_`f] Furthermore, due to `F33f`_`[combinatorial explosion`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Combinatorial_explosion]`_`f, according to Lei et al., "mining all frequent subtree patterns becomes infeasible for a large and dense tree database".`:cite-ref-zou06-10-0[`F5bf`_`[10`#cite-note-zou06-10]`_`f]
>>References
`:cite-note-chi01-1`!1.`! `F0af`_`[↑`#cite-ref-chi01-1-0]`_`f `:citerefchimuntznijssenkok2005`aChi, Yun; Muntz, Richard R.; Nijssen, Siegfried; Kok, Joost N. (28 June 2005). "Frequent Subtree Mining - An Overview". `*Fundamenta Informaticae`*. `!66`!: 161–198. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 14827585.
`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefdeepakfern-ndez-bacatirthapurasanderson2013`aDeepak, Akshay; Fernández-Baca, David; Tirthapura, Srikanta; Sanderson, Michael J.; McMahon, Michelle M. (July 2013). "EvoMiner: frequent subtree mining in phylogenetic databases". `*Knowledge and Information Systems`*. `!41`! (3): 559–590. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s10115-013-0676-0. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 254145982.
`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f Dai, H., Srikant, R. and Zhang, C. (2004). "Advances in Knowledge Discovery and Data Mining." `*8th Pacific-Asia Conference, PAKDD 2004, Sydney, Australia, May 26–28, 2004, Proceedings`*. 1st ed. p. 65.
`:cite-note-0-4`!4.`! `F0af`_`[↑`#cite-ref-0-4-0]`_`f `:citerefzaki2002`aZaki, Mohammed J. (2002). "Efficiently mining frequent trees in a forest". `*Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining`*. pp. 71–80. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1145/775047.775058. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-1581135671. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 1649653. Retrieved 16 June 2014.
`:cite-note-dee13-5`!5.`! `F0af`_`[↑`#cite-ref-dee13-5-0]`_`f Deepak, Akshay, David Fernández-Baca, Srikanta Tirthapura, Michael J. Sanderson, and Michelle M. McMahon. "EvoMiner: frequent subtree mining in phylogenetic databases." Knowledge and Information Systems (2011): 1-32.
`:cite-note-yun05-6`!6.`! `F0af`_`[↑`#cite-ref-yun05-6-0]`_`f Chi, Yun, Yirong Yang, and Richard R. Muntz. "Canonical forms for labelled trees and their applications in frequent subtree mining." `*Knowledge and Information Systems`* 8, no. 2 (2005): 203–234.
`:cite-note-chi04-7`!7.`! `F0af`_`[↑`#cite-ref-chi04-7-0]`_`f `:citerefchiyangmuntz2004`aChi, Yun; Yang, Yirong; Muntz, Richard R. (2004). "Mining Frequent Rooted Trees and Free Trees Using Canonical Forms" (PDF). `*Knowledge and Information Systems`*. Retrieved 16 June 2014.
`:cite-note-xia03-8`!8.`! `F0af`_`[↑`#cite-ref-xia03-8-0]`_`f `:citerefxiaoyaolidunham2003`aXiao, Yongqiao; Yao, Jenq-Foung; Li, Zhigang; Dunham, Margaret H. (2003). "Efficient data mining for maximal frequent subtrees". `*Third IEEE International Conference on Data Mining`*. ICDM 2003. pp. 379–386. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1109/ICDM.2003.1250943.
`:cite-note-9`!9.`! `F0af`_`[↑`#cite-ref-9]`_`f `:citerefaoki-kinoshita2009`aAoki-Kinoshita, Kiyoko F. (2009). `*Glycome Informatics: Methods and Applications`*. CRC Press. p. 141. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 9781420083347.
`:cite-note-zou06-10`!10.`! `F0af`_`[↑`#cite-ref-zou06-10-0]`_`f `:citerefzouluzhanghu2006`aZou, Lei; Lu, Yansheng; Zhang, Huaming; Hu, Rong (2006). "Mining Frequent Induced Subtree Patterns with Subtree-Constraint". `*Sixth IEEE International Conference on Data Mining Workshops`*. ICDM Workshops 2006. pp. 3–7. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1109/ICDMW.2006.112.
`c`F0af`_`[↑ Back to top`#top]`_`f`a